ABC250 D - 250-like Number

https://atcoder.jp/contests/abc250/tasks/abc250_d

提出

code: python

n = int(input())

# 素数p, qの探索 p < q / n, k <= 10^18

def ispirme(n):

if n <= 1: return False

for x in range(2, int(n ** 0.5) + 1):

if n % x == 0:

return False

return True

# 素数のリスト TLE

primes = i for i in range(pow(10, 5)) if ispirme(i)

ans = 0

for i in range(len(primes)):

for j in range(i+1, len(primes)):

if (primesi * pow(primesj, 3) <= n):

ans += 1

print(ans)

解答

code: python

def enum_primes(n):

prime_flag = 1 * (n + 1)

prime_flag0 = 0

prime_flag1 = 0

i = 2

while i * i <= n:

if prime_flagi:

for j in range(2 * i, n + 1, i):

prime_flagj = 0

i += 1

return [i for i in range(n + 1) if prime_flagi]

n = int(input())

ans = 0

primes = enum_primes(10 ** 6 + 5) # qは大きくても 10^6 よりは小さくなる

m = len(primes)

for i in range(m):

t = primesi ** 3 # 重い t = q ** 3を先に計算

for j in range(i): # primesi未満の素数を小さい順に全探索

if t * primesj > n: # 探索を打ち切る

break

ans += 1

print(ans)

テーマ

#primeDecomposition

メモ

【AtCoder解説】PythonでABC250のA,B,C,D,E問題を制する！

提出

TLE

code: python

import math

n = int(input())

# q < 1000000

# p は 2固定ではない

# 素数列挙？

def sieve_of_eratosthenes(n):

sieve = True * (n + 1)

sieve0, sieve1 = False, False

for i in range(2, int(n**0.5) + 1):

if sievei:

for j in range(i*i, n + 1, i):

sievej = False

return i for i, is_prime in enumerate(sieve) if is_prime

primes = sieve_of_eratosthenes(math.ceil(math.pow(n, 1/3)))

ans = 0

for i in range(1, len(primes)):

p = primes:i

for _p in p:

if _p * pow(primesi, 3) <= n:

ans += 1

else:

break

print(ans)

# product?

# 2, 3

# 2, 5

# 3, 5

# 2, 7

# 3, 7

# 5, 7

配列分割は時間がかかる

解答

code: python

import math

n = int(input())

def sieve_of_eratosthenes(n):

sieve = True * (n + 1)

sieve0, sieve1 = False, False

for i in range(2, int(n**0.5) + 1):

if sievei:

for j in range(i*i, n + 1, i):

sievej = False

return i for i, is_prime in enumerate(sieve) if is_prime

primes = sieve_of_eratosthenes(math.ceil(math.pow(n, 1/3)))

ans = 0

for i in range(len(primes)):

for j in range(i):

if primesj * pow(primesi, 3) <= n:

ans += 1

else:

break

print(ans)